package com.cltech.util;

import com.cltech.dto.TreeNode;
import org.apache.commons.collections.CollectionUtils;
import org.springframework.util.StringUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Administrator on 2019/4/6.
 */
public final class TreeUtil {

    public static List<? extends TreeNode> buildTree(List<? extends TreeNode> treeNodes) {
        List<TreeNode> roots = findRoots(treeNodes);
        List<TreeNode> notRoots = (List<TreeNode>) CollectionUtils.subtract(treeNodes, roots);
        for (TreeNode root : roots) {
            root.setChildren(findChildren(root, notRoots));
        }
        return roots;
    }

    private static List<TreeNode> findRoots(List<? extends TreeNode> allTreeNodes) {
        List<TreeNode> results = new ArrayList<TreeNode>();
        for (TreeNode node : allTreeNodes) {
            boolean isRoot = true;
            for (TreeNode comparedOne : allTreeNodes) {
                if (!StringUtils.isEmpty(node.getPid()) && node.getPid().equals(comparedOne.getKey())) {
                    isRoot = false;
                    break;
                }
            }
            if (isRoot) {
                node.setLevel(0);
                results.add(node);
                node.setRootId(node.getKey());
            }
        }
        return results;
    }

    private static List<TreeNode> findChildren(TreeNode root, List<TreeNode> allTreeNodes) {
        List<TreeNode> children = new ArrayList<TreeNode>();
        for (TreeNode comparedOne : allTreeNodes) {
            if (!StringUtils.isEmpty(comparedOne.getPid()) && comparedOne.getPid().equals(root.getKey())) {
                comparedOne.setParent(root);
                comparedOne.setLevel(root.getLevel() + 1);
                children.add(comparedOne);
            }
        }
        List<TreeNode> notChildren = (List<TreeNode>) CollectionUtils.subtract(allTreeNodes, children);
        for (TreeNode child : children) {
            List<TreeNode> tmpChildren = findChildren(child, notChildren);
            if (tmpChildren == null || tmpChildren.size() < 1) {
                child.setIsLeaf(true);
            } else {
                child.setIsLeaf(false);
            }
            child.setChildren(tmpChildren);
        }
        return children;
    }

    private static List<TreeNode> getLeafChildren(List<TreeNode> resultList, List<TreeNode> children) {
        for (TreeNode node : children) {
            if (node.getIsLeaf()) {
                resultList.add(node);
            } else {
                getLeafChildren(resultList, node.getChildren());
            }
        }
        return resultList;
    }
}
